import java.util.*;

public class Solution139 {

    String s;
    Set<String> wordSet;
    Map<Integer, Boolean> memory;

    private boolean dfs(int startInd){
        Boolean memRes = memory.get(startInd);
        if(memRes != null){ return memRes; }
        if(startInd == s.length()){return true;}
        StringBuilder sb = new StringBuilder();
        for (int i = startInd; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if(!wordSet.contains(sb.toString())){ continue; }
            boolean res = dfs(i + 1);
            memory.put(i + 1, res);
            if(res){ return true; }
        }
        return false;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.wordSet = new HashSet<>(wordDict);
        this.memory = new HashMap<>();
        return dfs(0);
    }

    public static void main(String[] args) {
        Solution139 s = new Solution139();
        s.wordBreak(
                "leetcode",
                        Arrays.asList("leet", "code"));
    }
}
